On-chip caches are used in various microprocessor designs to improve performance by storing frequently used information in fast on-chip cache memories. The performance is improved because information can be retrieved quickly during program execution. Some systems have multiple levels of cache. An “L1” cache typically is relatively small, but the access time is very fast. An “L2” cache is typically larger than the L1 cache, but has a slower access time than the L1 cache.
Upon encountering a “load” instruction, which attempts to retrieve data from a target memory location, the processor first determines whether the target data is already resident in the L1 cache. If the data is in the L1 cache (called a cache “hit”), then the target data is retrieved from the L1 cache. If the data is not in the L1 cache (a cache “miss”), the processor next determines whether the target data is in the L2 cache. If it is, then the target data is retrieved from the L2 cache. Finally, if the target data is in neither the L1 nor L2 caches, the target data is retrieved from system memory, which is larger and slower than either the L1 or L2 caches.
In some systems, a miss in the L1 cache for a load instruction will result in the target data being copied into the L1 cache from wherever it is currently located (L2 cache or system memory). In general, cache misses hurt performance but cache hits increase performance. In general, an L1 and/or L2 cache miss hurts processor performance as the processor must wait for data to return before executing subsequent instructions. By bringing the target data into the fastest L1 cache memory, any subsequent need for the data can be quickly satisfied from the L1 cache. While bringing the target data into the L1 cache is a fairly extensive process requiring multiple clock cycles, doing so may pay dividends upon subsequent accesses to the data once it is in the L1 cache. Performance may thereby be improved.
Cache systems take advantage of two effects—temporal locality and spatial locality. Temporal locality means that, once a piece of data is accessed, that same data is likely to be needed again in the near future. Spatial locality means that, once a piece of data is accessed, nearby data (e.g., data in contiguous memory locations) is likely to be accessed in the near future. When data is copied to the L1 cache, the target data, as well as contiguously surrounding data, is copied into a “line” of the L1 cache. This process improves system performance in the event that any of the nearby data is subsequently needed, which may occur in data sets with a high degree of spatial locality.
Data sets that have relatively low spatial and/or temporal locality tend to “pollute” cache memory. This means that some data may be stored in the cache, but is not likely to be needed in the near future. Such data occupies space which data that is more suitable for cache usage could otherwise occupy. This problem is particularly troublesome for L1 caches because of their relatively small size.